home *** CD-ROM | disk | FTP | other *** search
/ Almathera Ten Pack 3: CDPD 3 / Almathera Ten on Ten - Disc 3: CDPD3.iso / scope / 076-100 / scopedisk80 / mt / memory.doc < prev    next >
Text File  |  1995-03-19  |  7KB  |  159 lines
  1. Memory Management on the Amiga
  2.      by Fabbian G. Dufoe, III
  3.  
  4.      Because AmigaDOS is a multi-tasking operating system it requires a more
  5. complicated memory management scheme than most personal computer operating
  6. systems have.  Single-tasking systems can get by with setting the upper and
  7. lower limits of the free memory region.  With different processes starting
  8. and stopping independently free memory gets fragmented.  The system has to
  9. know where to find each fragment if it's to use memory efficiently.
  10.  
  11.      AmigaDOS keeps a list of available memory.  When a process needs RAM it
  12. asks the operating system to allocate some.  The system searches the memory
  13. free list to see if there is a big enough block available.  If so it
  14. allocates it to the process and removes it from the memory free list.  When
  15. the process frees the memory the system returns it to the memory free list. 
  16. The operating system doesn't keep track of which process allocated the
  17. memory, so if a process fails to return it there is no way to recover it
  18. without rebooting the system.
  19.  
  20.      Like everything in the Amiga's operating system, the path to the memory
  21. free list begins with a pointer to the exec library ExecBase structure.  The
  22. ExecBase structure and all the structures and lists the system uses for
  23. memory management are defined in the include files listed in the ROM Kernel
  24. Exec Manual.  These same files are supplied with your C compiler or
  25. assembler.   They are also available in the Native Developer's Kit available
  26. >from Commodore Amiga Technical Support (CATS).
  27.  
  28.      Opening the exec library returns a pointer to the ExecBase structure:
  29.  
  30.      struct ExecBase *ExecBase;
  31.      ExecBase = (struct ExecBase *)OpenLibrary("exec.library, 0L);
  32.  
  33.      The ExecBase structure is defined in exec/execbase.h.  One of the
  34. fields in the ExecBase structure is MemList.  It's a List structure that
  35. contains pointers to the list of memory regions which make up the memory
  36. free list.  There is a MemList structure documented in the ROM Kernel Manual
  37. and in exec/memory.h.  It is not related to the List structure named MemList
  38. in the ExecBase structure.  The similar names could easily confuse you.
  39.   
  40.      Exec/lists.h defines a List structure as follows:
  41.  
  42.      struct List { 
  43.          struct  Node *lh_Head;
  44.          struct  Node *lh_Tail;
  45.          struct  Node *lh_TailPred;
  46.          UBYTE   lh_Type;
  47.          UBYTE   l_pad;
  48.      };
  49.  
  50. The Node structure is defined in exec/nodes.h as follows:
  51.  
  52.      struct Node { 
  53.          struct  Node *ln_Succ;
  54.          struct  Node *ln_Pred;
  55.          UBYTE   ln_Type;
  56.          BYTE    ln_Pri; 
  57.          char    *ln_Name; 
  58.      };
  59.  
  60.      The memory free list is organized as a list of lists.  MemList points
  61. to a list of memory regions.  A region is a block of contiguous memory from
  62. which Exec can draw memory.  Each region is described by a MemHeader
  63. structure.  When the system is initialized it creates a region for chip RAM
  64. and one for each expansion RAM board in the system.
  65.  
  66.      If the expansion RAM boards occupy contiguous memory you can combine
  67. their regions into one with a program called MergeMem.  MergeMem is in the
  68. System directory of the 1.3 Workbench disk.
  69.  
  70.      The MemHeader structure is documented in exec/memory.h as follows:
  71.  
  72.      struct     MemHeader {
  73.          struct  Node mh_Node;
  74.          UWORD   mh_Attributes;     /* characteristics of this region */
  75.          struct  MemChunk *mh_First; /* first free region          */
  76.          APTR    mh_Lower;          /* lower memory bound          */
  77.          APTR    mh_Upper;          /* upper memory bound+1          */
  78.          ULONG   mh_Free;          /* total number of free bytes     */ 
  79.      };
  80.  
  81.      So the following gives the address of the first region in the memory
  82. free list:
  83.  
  84.      struct MemHeader *MemHeader;
  85.      MemHeader = (struct MemHeader *)ExecBase->MemList.lh_Head;
  86.  
  87.      The MemHeader structure begins with a Node structure (mh_Node) which
  88. links this region to the others in the system's memory free list.  Within
  89. the Node structure mh_Node.ln_Succ points to the next region and
  90. mh_Node.ln_Pred points to the preceding one.  In the first node in the list
  91. mh_Node.ln_Pred points to the head of the list (MemHeader == MemHeader-
  92. >mh_Node.ln_Pred).
  93.  
  94.      The MemHeader structure defines the upper (mh_Upper) and lower limits
  95. (mh_Lower) of the region and tells how many bytes it currently has available
  96. (mh_Free).  It contains a pointer to the first chunk of free memory
  97. (mh_First).
  98.  
  99.      Memory chunks are organized as a singly linked list.  The NewChunk
  100. structure (documented in exec/memory.h) contains the address of the next
  101. chunk in mc_Next and the number of bytes in this chunk in mc_Bytes:
  102.  
  103.      struct   MemChunk {
  104.          struct  MemChunk *mc_Next;   /* pointer to next chunk */
  105.          ULONG   mc_Bytes;      /* chunk byte size   */
  106.      };
  107.  
  108. A NULL pointer in mc_Next marks the end of the list.
  109.  
  110.      Before any memory is allocated from a region there will be just one
  111. chunk in the list.  The fields mh_First and mh_Lower will be equal and
  112. mh_Upper will be the same as mh_Free.  The smallest amount of memory that
  113. can be allocated is eight bytes.  That's because the smallest chunk of
  114. memory that can be replaced on the memory free list is eight bytes.  A
  115. MemChunk requires four bytes for mc_Next (a 32-bit address) and four bytes
  116. for mc_Bytes (an unsigned long integer).
  117.  
  118.      When the first block of memory is allocated from a region the size of
  119. the block is added to mh_First and mh_Free is reduced by the size of the
  120. block.  In the MemChunk structure mc_Next remains NULL and mc_Bytes is
  121. reduced by the amount of memory allocated.
  122.  
  123.      If a second block is allocated from the same region the size of the
  124. second block will be added to mh_First and subtracted from mh_Free and
  125. mc_Bytes.  There will still be just one chunk in the list, although it will
  126. be smaller.
  127.  
  128.      The first fragmentation of the region occurs when the first block is
  129. freed while the second remains allocated.  Then mh_First will be restored to
  130. its original value (equal to mh_Lower) and mh_Free will be increased by the
  131. size of the block.  The address pointed to by mh_First (which is mc_Next)
  132. will be loaded with the previous value of mh_First.  The size of the block
  133. will be loaded into mc_Bytes for the first MemChunk structure.
  134.  
  135.      Given Block1 as the size of the first block and Block2 as the size of
  136. the second block, the following relationships will be true after the first
  137. block is freed:
  138.  
  139.      mh_First == mh_Lower
  140.      mh_Upper == mh_Free + Block2
  141.      &mc_Next == mh_First
  142.      mc_Next == &mc_Next + Block1 + Block2
  143.      mc_Bytes == Block1
  144.      mc_Next->mc_Next == NULL
  145.      mc_Next->mc_Bytes == mh_Free - (Block1 + Block2)
  146.  
  147. When the last block is freed mh_Free will equal the difference between
  148. mh_Upper and mh_Lower, mc_Next will be set to NULL, and mc_Bytes will be the
  149. same as mh_Free.  In other words, the region will be restored to its
  150. original configuration with a single chunk that contains all the memory in
  151. the region.
  152.  
  153.      Chapter 6 of the Rom Kernel Manual: Exec describes the memory
  154. allocation routines Exec provides for programmers.  There are three pairs of
  155. routines.  AllocMem() and FreeMem() use the system's memory free list to
  156. manage one block per call.  AllocEntry() and FreeEntry() process multiple
  157. blocks with a single call.  Allocate() and Deallocate() allow you to manage
  158. blocks from a private memory free list.
  159.